/*
https://leetcode.cn/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/description/
*/
---------------------------------------------------------------

#include <vector>
#include <string>
#include <list>

using namespace std;

struct Graph {
    Graph(int cnt) : PointCnt(cnt) {
        edges.resize(cnt);
    }
    
    void addEdge(int from, int to) {
        edges[from].push_back(to);
    }

    void connect(int p1, int p2) {
        addEdge(p1, p2);
        addEdge(p2, p1);
    }

    int PointCnt;
    vector<list<int>> edges;
};

class Solution {
private:
    /**
     * 递归函数，用于遍历子树并统计相同标签的数量。
     *
     * @param graph 图结构
     * @param index 当前处理的节点索引
     * @param childs 每个标签在当前子树中的出现次数
     * @param labels 标签字符串
     * @param rst 结果数组，存储每个节点的结果
     */
    void getCnt(Graph& graph, int index, vector<int>& childs, string& labels, vector<int>& rst) {
        int label = labels[index] - 'a'; // 将字符转换为0-25的整数表示
        ++childs[label]; // 更新当前标签的计数
        rst[index] = childs[label]; // 初始化或更新结果
        
        for (auto child : graph.edges[index]) {
            if (rst[child] == 0) { // 确保不重复访问父节点
                vector<int> temp(26, 0); // 创建临时数组保存子节点的信息
                getCnt(graph, child, temp, labels, rst); // 递归调用
                
                // 更新当前节点的结果和标签计数
                rst[index] += temp[label];
                for (int i = 0; i < 26; ++i) {
                    childs[i] += temp[i];
                }
            }
        }
        
        --childs[label]; // 回溯时撤销对当前节点标签的计数
    }

public:
    /**
     * 计算每个节点的子树中与其自身标签相同的节点数量。
     *
     * @param n 节点总数
     * @param edges 边的列表
     * @param labels 标签字符串
     * @return 每个节点的结果
     */
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        Graph graph(n);
        vector<int> visited(n, 0); // 使用visited来代替原来的temp数组，更清晰地表达意图

        // 构建图，这里假设输入边不会形成环，并且至少有一条边连接到节点0
        for (auto& edge : edges) {
            graph.addEdge(edge[0], edge[1]);
        }

        vector<int> rst(n, 0); // 结果数组初始化为0
        vector<int> childs(26, 0); // 初始化标签计数器
        getCnt(graph, 0, childs, labels, rst); // 从根节点开始遍历
        return rst;
    }
};